
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-10-22
 * Time: 20:13
 */
class BinarySearchTree{
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
    }
    TreeNode root = null;
    public TreeNode search(int val){
        TreeNode cur = root;
        while (cur != null){
            if(cur.val < val){
               cur = cur.right;
            }else if(cur.val > val){
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }
    public boolean insert(int key){
        if(root == null){
            root = new TreeNode(key);
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null){
            if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key){
                parent = cur;
                cur = cur.left;
            }else {
                return false;
            }
        }
        TreeNode node = new TreeNode(key);
        if(key < parent.val){
            parent.left = node;
        }else {
            parent.right = node;
        }
        return true;
    }
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}
public class Main {
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
       int[] array ={5,3,4,1,7,8,2,6,9};
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.inorder(binarySearchTree.root);
    }

}
